package com.example.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 动态规划 ** 参考题解 **
 * 单词拆分
 * f(i) 为 true or false 是否能拆分
 * 记录str为最后的字符串
 */
public class Demo0139 {
    public static void main(String[] args) {
        String str="aaaaaaa";
        wordBreak1(str,Arrays.asList("aaaa","aaa"));
        String substring = str.substring(6, 7);
        System.out.println(substring);
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set=new HashSet<>(wordDict);
        int len=s.length();
        boolean f[] =new boolean[len+1];
        f[0]=true;
        for (int i = 1; i < len+1; i++) {
            for (int j = 0; j < i; j++) {
                //j前面为true j-i为true
                if (f[j] && set.contains(s.substring(j,i))){
                    f[i]=true;
                    break;
                }
            }
        }
        return f[len];
    }


    /**
     * 错误解法  考虑拆前拆后 aaaa aaa   aaaaaaa
     * @param s
     * @param wordDict
     * @return
     */
    public static boolean wordBreak1(String s, List<String> wordDict) {
        int len =s.length();
        Set<String> set=new HashSet<>(wordDict);
        int start=0,end=0;
        while (start<len && end <len+1){
            if (set.contains(s.substring(start,end))){
                start=end;
            }
            end++;
        }
        if (start==len){
            return true;
        }else {
            start=len;end=len;
            while (start>=0 && end>=0){
                if (set.contains(s.substring(start,end))) {
                    end=start;
                }
                start--;
            }
            return end==0;
        }
    }
}
